/**
 * @author ghp
 * @title 寻找两个正序数组的中位数
 */
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m == 0 && n == 0) {
            // 两个数组都为空时，直接返回0，防止后面出现NPE
            return 0;
        }

        // 合并数组
        int i = 0; // 用于遍历nums1
        int j = 0; // 用于遍历nums2
        int k = 0; // 用于遍历nums，构建新数组
        int[] nums = new int[m + n];
        while (i != m && j != n) {
            if (nums1[i] <= nums2[j]) {
                nums[k++] = nums1[i++];
            } else {
                nums[k++] = nums2[j++];
            }
        }
        // nums1还有元素
        while (i != m) {
            nums[k++] = nums1[i++];
        }
        // nums2还有元素
        while (j != n) {
            nums[k++] = nums2[j++];
        }

        // 求中位数
        int len = nums.length;
        if (len % 2 != 0) {
            // 奇数个元素时，中位数不需要求平均，直接返回
            return nums[len / 2];
        }
        return (double) (nums[len / 2] + nums[(len - 1) / 2]) / 2;
    }
}
